package greddy;

import java.util.Arrays;
import java.util.Comparator;

public class _13_435_无重叠区间 {
    public static int eraseOverlapIntervals(int[][] intervals) {
    	// 根据每个元素的左边界从小到大进行排序，每一个左边界都会比前一个的左边界大
    	Arrays.sort(intervals,new Comparator() {
			@Override
			public int compare(Object o1, Object o2) {
				int[] i = (int[])o1;
				int[] j = (int[])o2;
				Integer a = i[0];
				Integer b = j[0];
				return a.compareTo(b);
			}
    	});
    	
    	int count = 0;
    	for(int i = 1; i < intervals.length; i++) {
    		// 当前元素的左边界比上一个元素的右边界小，说明重叠了，则移除元素+1
    		// 并将当前元素的右边界设置为与前一个边界的最小值
    		// 这样下一个元素取前一个元素的右边界进行比较才是正确的
    		/*
    		 * 本题统计的是最少移除次数
    		 * 在一开始做的时候，我用了一个right用来保存上一次没被移除元素的右边界
    		 * 即当前元素不是重叠元素，则更新right值为其右边界，这样就不会统计到被移除元素的右边界
    		 * if(intervals[i][0] < intervals[i-1][1]) {count++} else {right = intervals[i][1]}
    		 * 但是这样有问题，比如 当 [1,2][3,6][4,5][7,12]
    		 * 通过判断可得[4,5]跟[3,6]重叠了，记录right=6，则继续判断，[7,12]与right不重叠，最终得到需要移除1个
    		 * 但是还有另一种可能性，比如移除[3,6]也是移除的最少数量，但是通过right方式，记录的只是移除[4,5]这种可能
    		 * 这种right方式在遇到特定的元素时，得到的将不会是移除的最少数量
    		 * 如果我们采用两个右边界的最小值作为右边界，则能保证能记录到最小移除次数
    		 * */
    		if(intervals[i][0] < intervals[i-1][1]) {
    			count++;
    			intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
    		}
    	}
    	
    	return count;
    }
    
    public static void main(String[] args) {
    	int[][] intervals = {{1,100},{11,22},{1,11},{2,12}};
    	System.out.println(eraseOverlapIntervals(intervals));
	}
}
